package hash;

import org.junit.Test;

import java.util.*;

/*
 *@description
 *@author hkfan
 *@version 1.0
 *@create 2025/5/26 16:23
 */
public class LeetCode_380 {
    @Test
    public void test(){
        RandomizedSet set = new RandomizedSet();
        System.out.println(set.insert(1));
        System.out.println(set.insert(10));
        System.out.println(set.insert(20));
        System.out.println(set.insert(30));
        System.out.println(set.getRandom());
        System.out.println(set.getRandom());
        System.out.println(set.getRandom());
        System.out.println(set.getRandom());
        System.out.println(set.getRandom());
    }

    class RandomizedSet {

        List<Integer> list;
        Map<Integer,Integer> map;

        public RandomizedSet() {
            list=new ArrayList<>();
            map = new HashMap<>();
        }

        public boolean insert(int val) {
            if (map.get(val)!=null){
                return false;
            }
            int index= list.size();
            list.add(val);
            map.put(val,index);
            return true;
        }

        public boolean remove(int val) {
            if (map.get(val)==null){
                return false;
            }
            if (list.size()==1){
                list.remove(0);
                map.remove(val);
                return true;
            }
            Integer index = map.get(val);
            list.set(index,list.get(list.size()-1));
            map.put(list.get(index),index);
            map.remove(val);
            list.remove(list.size()-1);

            return true;
        }

        public int getRandom() {
            int index = (int)(Math.random()*list.size());
            return list.get(index);
        }
    }

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */
}
